package sort;

import java.util.Arrays;

/**
 * @author RunningShrimp
 * @date 2021/6/9  15:21
 * @see <a href=""></a>
 */
@SuppressWarnings("unchecked")
public class MergeSort<E extends Comparable<E>> extends BaseSort<E> {


    public void sort1(E[] array) {
        sort(array, 0, array.length - 1);
    }

    private void sort(E[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        sort(array, start, mid);
        sort(array, mid + 1, end);
        merge(array, start, mid, end);
    }

    private void merge(E[] array, int l, int mid, int r) {
        E[] aux = (E[]) new Comparable[r - l + 1];
        if (r + 1 - l >= 0) {
            System.arraycopy(array, l, aux, 0, r + 1 - l);
        }
        System.out.println("aux:" + Arrays.toString(aux));
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                array[k] = aux[j - l];
                j++;
            } else if (j > r) {
                array[k] = aux[i - l];
                i++;
            } else if (less(aux[j - l], aux[i - l])) {
                array[k] = aux[i - l];
                i++;
            } else {
                array[k] = aux[j - l];
                j++;
            }
        }
    }

    @Override
    public void sort(E[] array) {
        for (int sz = 1; sz <= array.length; sz += sz) {
            for (int i = 0; i < array.length; i += sz * 2) {
                merge(array, i, i + sz - 1, Math.min(i + sz * 2 - 1, array.length - 1));
            }
        }
    }

    public static void main(String[] args) {
        Integer[] array = BaseSort.generateArray(8, 100);
        BaseSort<Integer> sort = new MergeSort<>();
        System.out.println("排序前：");
        sort.show(array);
        sort.sort(array);
        System.out.println("排序后");
        sort.show(array);
        System.out.println("是否有序：" + sort.isSorted(array));
    }
}
